﻿using Devil;
using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

namespace GameToolkit
{
    public class SortedQueue<T> : ICollection<T>
    {
        private bool mIsStructData;
        private int mLen;
        private T[] mDatas;
        private GetterDelegate<T, int> mQueueGetter;
        public GetterDelegate<T, int> QueueGetter
        {
            get { return mQueueGetter; }
            set
            {
                mQueueGetter = value == null ? DefaultQueue : value;
            }
        }
        private EquatableDelegate<T> mIsEqual;
        public EquatableDelegate<T> Equatable
        {
            get { return mIsEqual; }
            set
            {
                mIsEqual = value == null ? IsEqual : value;
            }
        }

        public SortedQueue(GetterDelegate<T, int> queueGeter, int initCapacity = 32, EquatableDelegate<T> equatable = null, bool alwaysAsValueType = false)
        {
            mQueueGetter = queueGeter == null ? DefaultQueue : queueGeter;
            mIsEqual = equatable == null ? IsEqual : equatable;
            mIsStructData = alwaysAsValueType || typeof(T).IsValueType;
            mDatas = new T[Mathf.Max(8, initCapacity)];
        }

        public int Count { get { return mLen; } }
        public T this[int index]
        {
            get { return mDatas[index]; }
        }
        public bool IsReadOnly { get { return false; } }
        public T[] ToArray()
        {
            var arr = new T[mLen];
            if (mLen > 0)
                Array.Copy(mDatas, arr, mLen);
            return arr;
        }

        int DefaultQueue(T v)
        {
            return 0;
        }

        bool IsEqual(T a, T b)
        {
            if (a == null)
                return b == null;
            else if (a is IEquatable<T>)
                return ((IEquatable<T>)a).Equals(b);
            else
                return a.Equals(b);
        }

        public IList<T> GetNextQueue(int index)
        {
            if (index >= mLen)
                return null;
            var q = mQueueGetter(mDatas[index]);
            for (int i = index + 1; i < mLen; i++)
            {
                var q1 = mQueueGetter(mDatas[i]);
                if (q1 != q)
                    return new SliceList<T>(mDatas, index, i - index);
            }
            return new SliceList<T>(mDatas, index, mLen - index);
        }

        public T FindQueue(int queue, FilterDelegate<T> filter)
        {
            int start = 0, end = mLen - 1;
            while (start <= end)
            {
                var c = (start + end) >> 1;
                var q = mQueueGetter(mDatas[c]);
                if (q < queue)
                {
                    start = c + 1;
                }
                else if (q > queue)
                {
                    end = c - 1;
                }
                else
                {
                    for (int i = c; i <= end; i++)
                    {
                        var item = mDatas[i];
                        if (filter == null || filter(item))
                            return item;
                    }
                    for (int i = c - 1; i >= start; i--)
                    {
                        var item = mDatas[i];
                        if (filter == null || filter(item))
                            return item;
                    }
                    return default;
                }
            }
            return default;
        }

        public int FirstIndexOfQueue(int queue)
        {
            int start = 0, end = mLen - 1;
            while (start <= end)
            {
                var c = (start + end) >> 1;
                var q = mQueueGetter(mDatas[c]);
                if (q < queue)
                {
                    start = c + 1;
                }
                else if (q > queue)
                {
                    end = c - 1;
                }
                else
                {
                    int index = c;
                    for (int i = c - 1; i >= start; i--)
                    {
                        if (mQueueGetter(mDatas[i]) == queue)
                            index = i;
                        else
                            break;
                    }
                    return index;
                }
            }
            return -1;
        }

        public int LastIndexOfQueue(int queue)
        {
            int start = 0, end = mLen - 1;
            while (start <= end)
            {
                var c = (start + end) >> 1;
                var q = mQueueGetter(mDatas[c]);
                if (q < queue)
                {
                    start = c + 1;
                }
                else if (q > queue)
                {
                    end = c - 1;
                }
                else
                {
                    int index = c;
                    for (int i = c + 1; i <= end; i++)
                    {
                        if (mQueueGetter(mDatas[i]) == queue)
                            index = i;
                        else
                            break;
                    }
                    return index;
                }
            }
            return -1;
        }

        public int IndexOf(T item)
        {
            var queue = mQueueGetter(item);
            int start = 0, end = mLen - 1;
            while (start <= end)
            {
                int c = (start + end) >> 1;
                var q = mQueueGetter(mDatas[c]);
                if (q < queue)
                {
                    start = c + 1;
                }
                else if (q > queue)
                {
                    end = c - 1;
                }
                else
                {
                    for (int i = c; i <= end; i++)
                    {
                        if (mIsEqual(item, mDatas[i]))
                            return i;
                    }
                    for (int i = c - 1; i >= start; i--)
                    {
                        if (mIsEqual(item, mDatas[i]))
                            return i;
                    }
                    break;
                }
            }
            return -1;
        }

        public void Add(T item)
        {
            if (mLen == mDatas.Length)
            {
                var arr = new T[mDatas.Length << 1];
                if (mLen > 0)
                    Array.Copy(mDatas, arr, mLen);
                mDatas = arr;
            }
            int start = 0, end = mLen - 1;
            int index = mLen++;
            var queue = mQueueGetter(item);
            while (start <= end)
            {
                int c = (start + end) >> 1;
                var q = mQueueGetter(mDatas[c]);
                if (q <= queue)
                {
                    index = c + 1;
                    start = index;
                }
                else
                {
                    index = c;
                    end = c - 1;
                }
            }
            for (int i = mLen - 1; i > index; i--)
            {
                mDatas[i] = mDatas[i - 1];
            }
            mDatas[index] = item;
        }

        public bool Remove(T item)
        {
            var i = IndexOf(item);
            if (i == -1)
                return false;
            RemoveAt(i);
            return true;
        }

        public void RemoveAt(int index)
        {
            if (index < 0 || index >= mLen)
                throw new IndexOutOfRangeException();
            mLen--;
            for (int i = index; i < mLen; i++)
            {
                mDatas[i] = mDatas[i + 1];
            }
            mDatas[mLen] = default;
        }

        public void Clear()
        {
            if (!mIsStructData)
            {
                for (int i = 0; i < mLen; i++)
                {
                    mDatas[i] = default;
                }
            }
            mLen = 0;
        }

        public bool Contains(T item)
        {
            return IndexOf(item) != -1;
        }

        public void CopyTo(T[] array, int arrayIndex)
        {
            Array.Copy(mDatas, 0, array, arrayIndex, Mathf.Min(mLen, array.Length - arrayIndex));
        }

        public IEnumerator<T> GetEnumerator()
        {
            return new Enumerator(this);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return new Enumerator(this);
        }

        internal struct Enumerator : IEnumerator<T>
        {
            SortedQueue<T> mQueue;
            int mIndex;
            public T Current { get { return mQueue.mDatas[mIndex]; } }

            object IEnumerator.Current { get { return mQueue.mDatas[mIndex]; } }

            public Enumerator(SortedQueue<T> queue)
            {
                mQueue = queue;
                mIndex = -1;
            }

            public void Dispose()
            {
                mQueue = null;
            }

            public bool MoveNext()
            {
                return ++mIndex < mQueue.mLen;
            }

            public void Reset()
            {
                mIndex = -1;
            }
        }
    }
}